package exercises.newcoder.solution;

import exercises.newcoder.util.TreeNode;

/**
 * <a href="https://www.nowcoder.com/practice/1b0b7f371eae4204bc4a7570c84c2de1?tpId=188&&tqId=38623&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC16 判断二叉树是否对称</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 描述
 * 给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
 * <p>
 * 备注：
 * <p>
 * 你可以用递归和迭代两种方法解决这个问题
 *
 * @author or2
 * @date 2021年09月30日 时间: 9:10
 */
public class NC16 {
    /**
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;

        return checkSymmetry(root.left, root.right);
    }

    private boolean checkSymmetry(TreeNode left, TreeNode right) {
        if (left == null)
            return right == null;

        if (right == null)
            return false;

        if (left.val != right.val)
            return false;

        return checkSymmetry(left.left, right.right) && checkSymmetry(left.right, right.left);
    }
}
